from gen import generate_data
from alg import Solution

def test_algorithm():
    # 示例测试
    test_cases = [
        ([1,3,5,7,2,4,6,8], 4, [1,2,3,4]),
        ([], 0, []),
        ([5,5,5,5], 2, [5,5]),
        ([10,9,8,7,6], 5, [6,7,8,9,10])
    ]
    sol = Solution()
    for arr, k, expected in test_cases:
        res = sorted(sol.smallestK(arr, k))
        print(f"原始数据: {arr}, k={k}")
        print(f"分治法结果(k={k}): {res}")
        print(f"期望结果: {expected}\n")
        assert res == expected, f"分治法失败: {arr}, k={k}"

    # 随机数据测试
    for _ in range(5):
        arr, k = generate_data()
        expected = sorted(arr)[:k]
        result = sorted(sol.smallestK(arr, k))
        print(f"随机数据: {arr[:20]}... (共{len(arr)}项), k={k}")
        print(f"分治法最小k个数(k={k}): {result}")
        print(f"期望: {expected}\n")
        assert result == expected, f"分治法失败: {arr}, k={k}"
    print("所有测试通过")

if __name__ == "__main__":
    test_algorithm()